﻿#include"avltree.h"

static unsigned char left_rotate_avltree(TreeNode** node) {
    TreeNode *son, *pson;
    son = (*node)->right;
    pson = son->left;

    if (son->bf ^ 1) {
        (*node)->right = son->left;
        son->left = *node;
        *node = son;
        return 1;
    }

    son->left = pson->right;
    pson->right = son;
    (*node)->right = pson->left;
    pson->left = *node;
    *node = pson;
    return 0;
}


static unsigned char right_rotate_avltree(TreeNode** node) {
    TreeNode *son, *pson;
    son = (*node)->left;
    pson = son->right;

    if (son->bf ^ 2) {
        (*node)->left = son->right;
        son->right = *node;
        *node = son;
        return 2;
    }

    son->right = pson->left;
    pson->left = son;
    (*node)->left = pson->right;
    pson->right = *node;
    *node = pson;
    return 0;
}

static void balance_factory_avltree(TreeNode* node,unsigned char rt,unsigned char* ub) {
    TreeNode *left_node, *right_node;

    //根节点的左子节点
    left_node = node->left;
    //根节点的右子节点
    right_node = node->right;

    unsigned char rotate_type = ((rt != 0) | (node->bf << 1));
    if (node->bf != 0)
        node->bf = 0;
    switch (rotate_type) {
        case 0:
            left_node->bf = right_node->bf = 0;
            break;
        case 1:
            node->bf = rt;
            *ub = 0;
            break;
        case 2:
            left_node->bf = 0;
            right_node->bf = 2;
            break;
        case 3:
            right_node->bf = 0;
            break;
        case 4:
            right_node->bf = 0;
            left_node->bf = 1;
            break;
        default:
            left_node->bf = 0;
    }
}


void* insert_avltree(AvlTree* tree,void* data,size_t data_len,int(*cmp)(void*,void*)) {
    TreeNode **cp_head = &tree->head;
    unsigned char direction_stack[MAX_STACK_HIGH];
    TreeNode **node_pp_stack[MAX_STACK_HIGH];
    unsigned char stack_len = 0;
    unsigned char new_height;
    unsigned char rt;
    int cmp_result;

    while (*cp_head) {
        cmp_result = cmp(data, (*cp_head)->data);

        if (cmp_result == 0)
            return (*cp_head)->data;

        node_pp_stack[stack_len] = cp_head;
        if (cmp_result > 0) {
            direction_stack[stack_len] = 1;
            cp_head = &(*cp_head)->right;
        } else {
            direction_stack[stack_len] = 0;
            cp_head = &(*cp_head)->left;
        }
        ++stack_len;
    }

    new_height = stack_len + 1;

    *cp_head = (TreeNode *) malloc(sizeof(TreeNode));
    if (*cp_head == NULL)
        return NULL;

    if (data_len) {
        (*cp_head)->data = malloc(data_len);
        if ((*cp_head)->data == NULL) {
            free(*cp_head);
            return NULL;
        }
        memcpy((*cp_head)->data, data, data_len);
    } else
        (*cp_head)->data = data;

    (*cp_head)->bf = 0;
    (*cp_head)->left = (*cp_head)->right = NULL;

    ++tree->node_count;

    while (stack_len > 0) {
        cp_head = node_pp_stack[--stack_len];
        rt = direction_stack[stack_len] | ((*cp_head)->bf << 1);

        switch (rt) {
            case 0:
            case 1:
                (*cp_head)->bf = direction_stack[stack_len] + 1;
                break;
            case 2:
                rt = right_rotate_avltree(cp_head);
                goto Tk_Ba;
            case 3:
            case 4:
                (*cp_head)->bf = 0;
                return (*cp_head)->data;
            default:
                rt = left_rotate_avltree(cp_head);
            Tk_Ba:
                balance_factory_avltree(*cp_head, rt, NULL);
                return (*cp_head)->data;
        }
    }

    if (new_height > tree->height)
        tree->height = new_height;
    return (*cp_head)->data;
}


void* delete_node_avltree(AvlTree* tree,void* data,int(*cmp)(void*,void*)) {
    TreeNode **cp_head = &tree->head;
    TreeNode **delete_node, *last_leap;
    unsigned char direction_stack[MAX_STACK_HIGH];
    TreeNode **node_pp_stack[MAX_STACK_HIGH];
    void *del_data;//存放删除的节点的数据指针
    int cmp_result;

    unsigned char stack_len, delete_index, unbalance;
    unsigned char rt;

    if (*cp_head == NULL)
        return NULL;

    stack_len = 0;
    unbalance = 1;

    while (*cp_head) {
        //获取待删除键值与节点键值的比较结果
        cmp_result = cmp(data, (*cp_head)->data);

        //存在相同的比较结点，退出迭代
        if (cmp_result == 0)
            break;

        //将当前链接存入堆栈
        node_pp_stack[stack_len] = cp_head;

        //根据比较结果，保存下钻的方向，并移动指向链接的指针
        if (cmp_result > 0) {
            direction_stack[stack_len] = 0;//在删除的实现中，用0表示向右下方向移动
            cp_head = &(*cp_head)->right;
        } else {
            direction_stack[stack_len] = 1;//用1表示向左下方向移动
            cp_head = &(*cp_head)->left;
        }
        ++stack_len;//栈高度+1
    }

    if (cmp_result != 0)
        return NULL;

    //存放指向待删除节点的链接
    node_pp_stack[stack_len] = cp_head;

    //保存指向待删除节点的链接
    delete_node = cp_head;

    //若待删除节点的左节点不为空
    if ((*cp_head)->left != NULL) {

        //将待删除节点的下支方向定位到左边
        direction_stack[stack_len++] = 1;

        //将待删除节点的左支的下支方向定向到右边
        direction_stack[stack_len] = 0;

        //保存待删除节点的下一个堆栈位置
        delete_index = stack_len++;

        //将当前链接定位到待删除节点的左节点的右节点的位置
        cp_head = &(*cp_head)->left->right;

        //若链接不指向空，则将当前链接存入堆栈，并继续向当前链接指向的节点的右支移动
        while (*cp_head) {
            node_pp_stack[stack_len] = cp_head;
            direction_stack[stack_len++] = 0;
            cp_head = &(*cp_head)->right;
        }

        //回退一个堆栈位置
        --stack_len;
        //若待删除节点的下一个堆栈位置等于当前位置，则说明待删除节点的左节点作为替换节点
        if (stack_len == delete_index)
            //用指针保存替换节点
            last_leap = (*delete_node)->left;
        else {
            //末尾堆栈节点即为替换节点
            last_leap = *node_pp_stack[stack_len];
            //将指向替换节点的链接定向到替换节点的左支
            *node_pp_stack[stack_len] = last_leap->left;
            //将替换节点的左支定向到待删除节点的左支
            last_leap->left = (*delete_node)->left;
            //将保存指向替换节点的左支的链接到堆栈中待删除结点下一个的位置堆栈
            node_pp_stack[delete_index] = &last_leap->left;
        }
        //将替换节点的右支定向到待删除节点的右支
        last_leap->right = (*delete_node)->right;
        //将替换节点的平衡度等于待删除节点的平衡度
        last_leap->bf = (*delete_node)->bf;
    } else if ((*cp_head)->right != NULL) //若待删除节点的右节点不为空，则将其右节点地址写入到替换节点的值
        last_leap = (*delete_node)->right;
    else//待删除节点是叶子节点，替换节点指向空
        last_leap = NULL;

    del_data = (*delete_node)->data;
    free(*delete_node);

    tree->node_count--;
    //将指向待删除节点的链接重新定向为替换节点的地址
    *delete_node = last_leap;

    //开始往上回溯进行平衡旋转
    while (stack_len > 0) {
        //用delete_node保存链接的信息
        delete_node = node_pp_stack[--stack_len];

        //获取状态参数
        rt = direction_stack[stack_len] | ((*delete_node)->bf << 1);

        switch (rt) {
            case 0://0或1表示回溯节点的平衡因子是0，不会因为其子树的删除改变该节点的平衡
            case 1:
                (*delete_node)->bf = direction_stack[stack_len] + 1;
                return del_data;//
            case 2://表示回溯节点发生了过度左倾，需要进行右旋
                rt = right_rotate_avltree(delete_node);
                goto Tk_Ba;//完成旋转后跳转到计算平衡因子值的函数入口
            case 3://3或4表示回溯节点的平衡因子与其下钻方向相反，回溯节点的平衡因子归0
            case 4:
                (*delete_node)->bf = 0;
                break;
            default://默认情况，与情况2相反
                rt = left_rotate_avltree(delete_node);
            Tk_Ba://对进行过旋转的节点重新计算其与孙子节点的平衡因子
                balance_factory_avltree(*delete_node, rt, &unbalance);
                if (!unbalance)//若旋转过后并不会导致树的高度发生变化，则可以退出
                    return del_data;
        }
    }

    //若删除的过程能够到达此处，说明树高必定减少
    //树高-1
    --tree->height;

    return del_data;
}


void* find_avltree(AvlTree* tree,void* data,int(*cmp)(void*,void*)) {
    TreeNode *node = tree->head;
    int cmp_result;//保存比较结果
    //若节点不为空，则可以继续查找
    while (node) {
        //根据比较接口获取比较结果
        cmp_result = cmp(data, node->data);

        //若结果为0，说明找到了节点，返回节点的值域指针
        if (cmp_result == 0)
            return node->data;
        //若比较结果大于0，说明待查找的值必定在右支
        if (cmp_result > 0)
            node = node->right;
        else//否则在左支
            node = node->left;
    }
    //当迭代到空节点时，说明查找失败，返回空指针
    return NULL;
}



void destroy_avltree(AvlTree* tree,int is_free) {
    //空树，直接退出
    TreeNode *head = tree->head;
    TreeNode *node_stack[MAX_STACK_HIGH];

    if (head == NULL)
        return;

    //保存上层结点的堆栈；临时变量
    TreeNode *temp;
    //堆栈的长度
    unsigned char stack_len = 0;

    do {
        while (head->left) {//若当前节点的左支不为空，则将其链接保存到堆栈，然后移动到节点的左支链接
            node_stack[stack_len++] = head;
            head = head->left;
        }

        //保存最后一个左链接为空的结点的右链接
        temp = head->right;

        //释放节点内存
        if (is_free)
            free(head->data);
        free(head);

        //被释放内存的结点的右链接不为空，将当前结点定向到被释放内存的结点的右链接
        if (temp)
            head = temp;
        else {
            //堆栈为空，完成迭代，退出
            if (stack_len == 0)break;
            do {
                //从堆栈中取出结点，保存其右链接并释放被取出的结点的内存
                head = node_stack[--stack_len];
                temp = head->right;
                //
                if (is_free)
                    free(head->data);
                free(head);
            } while (temp == NULL && stack_len != 0);//若被取出的结点的右链接为空，并且堆栈不为空，则继续取出结点

            //若被取出的结点的右链接为空，则迭代完成，退出
            if (temp == NULL)
                break;
            head = temp;//将当前结点定向到被取出结点的右链接
        }
    } while (1);

    //将树的高度和节点数量以及头指针都重置为0
    tree->node_count = 0;
    tree->height = 0;
    tree->head = NULL;
}


void init_avltree(AvlTree* tree) {
    tree->head = NULL;
    tree->height = 0;
    tree->node_count = 0;
}


void init_iterator_avltree(AvlTree* tree,AvlIterator* iterator,int begin_direction) {
    //无节点，设置为状态3
    if (tree->head == NULL) {
        iterator->status = 3;
        return;
    }

    //初始化栈的长度和当前高度信息
    iterator->stack_prev_len = MAX_STACK_HIGH - 1;
    iterator->stack_next_len = 0;
    iterator->cur_height = 0;

    //按照所传入的方向进行入栈
    TreeNode *node = tree->head;
    if (!begin_direction) {
        //设置状态为边界情况
        iterator->status = 1;
        do {
            node->height = iterator->cur_height;
            if (node->left == NULL)
                break;
            iterator->stack_tow_way[iterator->stack_next_len++] = node;
            node = node->left;
            ++iterator->cur_height;
        } while (1);
    } else {
        iterator->status = 2;
        do {
            node->height = iterator->cur_height;
            if (node->right == NULL)
                break;
            iterator->stack_tow_way[iterator->stack_prev_len--] = node;
            node = node->right;
            ++iterator->cur_height;
        } while (1);
    }
    iterator->cur_node = node;
}

/**
 * 返回当前迭代器所指向的下一个位置
 * @param iterator 迭代器的指针
 * @return 如果下一个位置存在数据，那么返回下一个节点的数据指针
 *  否则返回NULL
 */
void* next_avltree(AvlIterator* iterator) {
    TreeNode *cur_node;
    switch (iterator->status) {
        case 0://正常迭代，不处于边界情况
            cur_node = iterator->cur_node;
            if (cur_node->right) {
                iterator->stack_tow_way[iterator->stack_prev_len--] = cur_node;
                cur_node = cur_node->right;
                do {
                    ++iterator->cur_height;
                    cur_node->height = iterator->cur_height;
                    if (cur_node->left == NULL)
                        break;
                    iterator->stack_tow_way[iterator->stack_next_len++] = cur_node;
                    cur_node = cur_node->left;
                } while (1);
            } else if (iterator->stack_next_len != 0) {
                cur_node = iterator->stack_tow_way[--iterator->stack_next_len];
                iterator->stack_prev_len += iterator->cur_height - cur_node->height - 1;
                iterator->cur_height = cur_node->height;
            } else {
                iterator->status = 2;
                return NULL;
            }
            iterator->cur_node = cur_node;
            return cur_node->data;
        case 1://当所在节点位于第一个节点之前，直接返回第一个节点，并设置status=0
            iterator->status = 0;
            return iterator->cur_node->data;
        default://当所在的节点位于最后一个节点之后(对应status=2),或者树为空(对应status=3)，那么直接返回NULL
            return NULL;
    }
}


void* prev_avltree(AvlIterator* iterator) {

    TreeNode *cur_node;
    switch (iterator->status) {
        case 0://正常迭代，不处于边界情况
            cur_node = iterator->cur_node;
            if (cur_node->left) {
                iterator->stack_tow_way[iterator->stack_next_len++] = cur_node;
                cur_node = cur_node->left;

                do {
                    ++iterator->cur_height;
                    cur_node->height = iterator->cur_height;
                    if (cur_node->right == NULL)
                        break;
                    iterator->stack_tow_way[iterator->stack_prev_len--] = cur_node;
                    cur_node = cur_node->right;
                } while (1);
            } else if (iterator->stack_prev_len != MAX_STACK_HIGH - 1) {
                cur_node = iterator->stack_tow_way[++iterator->stack_prev_len];
                iterator->stack_next_len -= iterator->cur_height - cur_node->height - 1;
                iterator->cur_height = cur_node->height;
            } else {
                iterator->status = 1;
                return NULL;
            }
            iterator->cur_node = cur_node;
            return cur_node->data;
        case 1://当所在的节点位于第一个节点之前
            return NULL;
        case 2://当所在节点位于最后一个节点之后，直接返回最后一个节点，并设置status=0
            iterator->status = 0;
            return iterator->cur_node->data;
        default://或者树为空，那么直接返回NULL
            return NULL;
    }
}

void* find_into_iterator_avltree(AvlTree* tree,void* data,int(*cmp)(void*,void*),AvlIterator* iterator) {
    iterator->cur_height = 0;
    iterator->stack_prev_len = MAX_STACK_HIGH - 1;
    iterator->stack_next_len = 0;
    iterator->cur_height = 0;

    TreeNode *cur_node = tree->head;

    while (cur_node) {
        cur_node->height = iterator->cur_height;
        int result = cmp(data, cur_node->data);
        if (result == 0)
            break;

        ++iterator->cur_height;
        if (result < 0) {
            iterator->stack_tow_way[iterator->stack_next_len++] = cur_node;
            cur_node = cur_node->left;
        } else {
            iterator->stack_tow_way[iterator->stack_prev_len--] = cur_node;
            cur_node = cur_node->right;
        }
    }

    if (cur_node == NULL) {
        iterator->status = 3;
        return NULL;
    }

    iterator->cur_node = cur_node;
    iterator->status = 0;
    return cur_node->data;
}